#ifndef __BINARYTREE_H__
#define __BINARYTREE_H__

using ElementType = int;
class BinaryTree
{
public:
    // 无参构造
    BinaryTree();
    // 析构
    ~BinaryTree();

    // 插入
    void Insert(const ElementType &element);
    // show
    void show();
    // 找节点
    ElementType *FindElement(const ElementType &element);
    // 删除节点
    void RemoveByElement(const ElementType &element);
    
private:
    struct TreeNode
    {
        TreeNode(const ElementType &element)
        {
            value = element;
            left = right = parent = nullptr;
        }
        ElementType value; // 数据域
        TreeNode *left; // 左孩子
        TreeNode *right; // 右孩子
        TreeNode *parent; // 双亲
    };
    // 插入（递归）
    TreeNode *InsertNode(TreeNode *node, const ElementType &element);
    // 前序遍历
    void PrevTravel(TreeNode *node);
    // 中序遍历
    void MidTravel(TreeNode *node);
    // 后序遍历
    void PostTravel(TreeNode *node);
    // 释放（递归）
    void FreeNode(TreeNode *node);
    // 找节点
    ElementType *FindNode(TreeNode *node, const ElementType &element);
    // 删除节点
    TreeNode *RemoveNode(TreeNode *node, const ElementType & element);
    // 获取一棵树中的最小值点
    TreeNode *GetMinNode(TreeNode *node);

    // 右旋
    TreeNode *RotateRight(TreeNode *node);
    // 左旋
    TreeNode *RotateLeft(TreeNode *node);
    // 左右旋
    TreeNode *RotateLeftRight(TreeNode *node);
    // 右左旋
    TreeNode *RotateRightLeft(TreeNode *node);
    
    // 获取树的高度
    int GetNodeHeight(TreeNode *node);
    // 左右子树高度差
    int LRDvtion(TreeNode *node);
    TreeNode *root; // 根节点 
};


#endif